#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#define DEBUG 0
#define USENEXTPERMUTATION 0
#define ISPROBLEM10098 1

using namespace std;

vector <string> permutations;

string stringLowerCase(string s)
{
  string r = "";
  for(int i=0; i<s.size(); i++)
  {
    if(s[i] < 97)
      r+=(s[i] + 32);
    else
      r+=s[i];
  }
  return r;
}

bool stringCompareFor195(char a, char b)
{
   string sa, sb;
   sa += a;
   sb += b;
   if(stringLowerCase(sa) == stringLowerCase(sb))
      return sa < sb;
   else
      return stringLowerCase(sa) < stringLowerCase(sb);
}

void doPermutations(string chars, string permutation)
{
    if(chars.size() == 1)
    {
       permutations.push_back(permutation + chars);
       return;
    }
    
    if(DEBUG) cout<<"chars = "<<chars<<endl;
    
    string prevletter = "";
    
    for(int i = 0; i < chars.size(); i++)
    {
         if(prevletter == chars.substr(i,1)) continue;
         
         prevletter = chars.substr(i,1);
         
         doPermutations(
                        chars.substr(0,i) + chars.substr(i+1),
                        permutation + chars[i]
                        );
    }
}

int main ()
{
   int n;
   string word;
   
   cin>>n;
   
   while(n--)
   {
      cin>>word;
      
      if(ISPROBLEM10098)
         sort(word.begin(), word.end());
      else
         sort(word.begin(), word.end(), stringCompareFor195);
         
      if(USENEXTPERMUTATION)
      {
         if(ISPROBLEM10098)
            do
               cout<<word<<endl;
            while(next_permutation(word.begin(), word.end()));
         else
            do
               cout<<word<<endl;
            while(next_permutation(word.begin(), word.end(), stringCompareFor195));
         if(ISPROBLEM10098) cout<<endl;
      }         
      else
      {
         permutations.clear();
         
         doPermutations(word, "");
         
         for(int i = 0; i < permutations.size(); i++)
            cout<<permutations[i]<<endl;
         if(ISPROBLEM10098) cout<<endl;
      }
   }
   return 0;
}
